package org.aplombh.java.utils;

import java.util.HashMap;
import java.util.Stack;

public class ExpressionEvaluation {
    private final Stack<Integer> num;
    private final Stack<Character> op;
    private final HashMap<Character, Integer> pr;

    public ExpressionEvaluation() {
        num = new Stack<>();
        op = new Stack<>();
        pr = new HashMap<>();

        // 存储优先级
        pr.put('+', 1);
        pr.put('-', 1);
        pr.put('*', 2);
        pr.put('/', 2);
    }

    public String evaluate(String str) {

        // 遍历字符串中每一个元素
        for (int i = 0; i < str.length(); i++) {
            // 取出每一个元素
            char c = str.charAt(i);
            // 如果元素为值
            if (isdigit(c)) {
                // 将该值取出
                int x = 0, j = i;
                // 如果值大于9，计算出该数
                while (j < str.length() && isdigit(str.charAt(j)))
                    x = x * 10 + str.charAt(j++) - '0';
                // 将该数压入栈中
                num.push(x);
                // 计算过程中多加了一次，要减掉
                i = j - 1;
            } else if (c == '(') op.push(c);  // 如果为左括号，入栈
            else if (c == ')') {
                // 如果为右括号，将op一直弹出，直到遇到一个左括号
                while (op.peek() != '(') eval();
                // 将左括号弹出
                op.pop();
            } else {  // 其他情况，为运算符号
                // 如果当前运算符号合法，弹出op中所有比当前运算符优先级高的所有运算符
                while (op.size() != 0 && pr.containsKey(op.peek()) && pr.get(op.peek()) > pr.get(c)){
                    eval();
                }
                // 将当前运算符入栈
                op.push(c);
            }
        }
        // 将所有无优先级区分的所有运算计算出来
        while (op.size() != 0) eval();

        // 将运算结果出队
        return num.peek().toString();
    }

    private void eval() {
        // num弹出两个元素参与运算，op弹出操作符
        int b = num.peek();
        num.pop();
        int a = num.peek();
        num.pop();
        char c = op.peek();
        op.pop();
        int x;
        // 根据操作符类型计算结果
        switch (c) {
            case '+':
                x = a + b;
                break;
            case '-':
                x = a - b;
                break;
            case '*':
                x = a * b;
                break;
            default:
                x = a / b;
                break;
        }
        // 将结果压入num中
        num.push(x);
    }

    private boolean isdigit(char c) {
        // 判断是否为数字符号
        return c >= '0' && c <= '9';
    }
}
